/*
 * Copyright © 2009 Perseus Project - Tufts University <http://www.perseus.tufts.edu>
 *
 * This file is part of UniCollatorPerseus.
 *
 * AlignmentPerseus is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * AlignmentPerseus is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * You should have received a copy of the GNU General Public License
 * along with AlignmentPerseus.  If not, see <http://www.gnu.org/licenses/>.
 */

package eu.himeros.alignment;

import java.util.Vector;

/**
 * Perform alignment of strings contained in arrays.
 *
 * @author Federico Boschetti <federico.boschetti.73@gmail.com>
 */
public class StringArrayAligner extends Aligner {
    protected Vector<String> vect1 = new Vector<String>(100);
    protected Vector<String> vect2 = new Vector<String>(100);
    protected String[][] alignedStrings = null;

    /**
     * Default Constructor.
     */
    public StringArrayAligner() {}

    /**
     * Constructor that set the Similarity Evaluator.
     *
     * @param simEval the Similarity Evaluator.
     */
    public StringArrayAligner(SimEvaluator simEval) {
        this.simEval = simEval;
    }

    /**
     * Align the string arrays.
     *
     * @param strs1 the first string array.
     * @param strs2 the second string array.
     * @return the result of alignment.
     */
    public String[][] align(String[] strs1, String[] strs2) {
        //Similarity matrix
        double[][] simMatrix = new double[strs1.length][strs2.length];
        double[][] matrix = new double[strs1.length + 1][strs2.length + 1];
        for (int i = 0; i < strs1.length; i++) {
            for (int j = 0; j < strs2.length; j++) {
                simMatrix[i][j] = simScore(strs1[i], strs2[j]);
            }
        }
        matrix[0][0] = 0;
        //Fill matrix marginals
        for (int i = 1; i <= strs1.length; i++) {
            matrix[i][0] = i * gapPenalty;
        }
        for (int j = 1; j <= strs2.length; j++) {
            matrix[0][j] = j * gapPenalty;
        }
        double scoreDown = 0;
        double scoreRight = 0;
        double scoreDiag = 0;
        double bestScore = 0;
        //Fill matrix
        for (int i = 1; i <= strs1.length; i++) {
            for (int j = 1; j <= strs2.length; j++) {
                scoreDown = matrix[i - 1][j] + gapPenalty;
                scoreRight = matrix[i][j - 1] + gapPenalty;
                scoreDiag = matrix[i - 1][j - 1] + simMatrix[i - 1][j - 1];
                bestScore = Math.max(Math.max(scoreDown, scoreRight), scoreDiag);
                matrix[i][j] = bestScore;
            }
        }
        //Backtrack the path
        int i = strs1.length, j = strs2.length;
        double score = 0, scoreLeft = 0, scoreDiagInv = 0;
        while (i > 0 && j > 0) {
            score = matrix[i][j];
            scoreDiagInv = matrix[i - 1][j - 1];
            scoreLeft = matrix[i - 1][j];
            if (score == scoreDiagInv + simMatrix[i - 1][j - 1]) {
                makeAlignment(strs1[i - 1], strs2[j - 1]);
                i = i - 1;
                j = j - 1;
            } else if (score == scoreLeft + gapPenalty) {
                makeAlignment(strs1[i - 1], null);
                i = i - 1;
            } else {
                makeAlignment(null, strs2[j - 1]);
                j = j - 1;
            }
        }
        while (i > 0) {
            makeAlignment(strs1[i - 1], null);
            i = i - 1;
        }
        while (j > 0) {
            makeAlignment(null, strs2[j - 1]);
            j = j - 1;
        }
        return makeResult();
    }

    /**
     * Add strings to the result vectors.
     *
     * @param str1 the first string.
     * @param str2 the second string.
     */
    private void makeAlignment(String str1, String str2) {
        vect1.add(str1);
        vect2.add(str2);
    }

    /**
     * Make the result.
     *
     * @return the result matrix.
     */
    private String[][] makeResult() {
        alignedStrings = new String[2][vect1.size()];
        vect1.copyInto(alignedStrings[0]);
        vect2.copyInto(alignedStrings[1]);
        return alignedStrings;
    }

    /**
     * Evaluate the similarity score.
     *
     * @param sms1 the first string.
     * @param sms2 the second string.
     * @return the similarity score.
     */
    protected double simScore(String sms1, String sms2) {
        return simEval.eval(sms1, sms2);
    }

}
